<?php
/*
 *    $Id: NestedSet.php 7490 2010-03-29 19:53:27Z jwage $
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * This software consists of voluntary contributions made by many individuals
 * and is licensed under the LGPL. For more information, see
 * <http://www.doctrine-project.org>.
 */

/**
 * Doctrine_Node_NestedSet
 *
 * @package    Doctrine
 * @subpackage Node
 * @license    http://www.opensource.org/licenses/lgpl-license.php LGPL
 * @link       www.doctrine-project.org
 * @since      1.0
 * @version    $Revision: 7490 $
 * @author     Joe Simms <joe.simms@websites4.com>
 * @author     Roman Borschel <roman@code-factory.org>
 */
class Doctrine_Node_NestedSet extends Doctrine_Node implements Doctrine_Node_Interface
{
	/**
	 * test if node has previous sibling
	 *
	 * @return bool
	 */
	public function hasPrevSibling()
	{
		return $this->isValidNode($this->getPrevSibling());
	}

	/**
	 * test if node has next sibling
	 *
	 * @return bool
	 */
	public function hasNextSibling()
	{
		return $this->isValidNode($this->getNextSibling());
	}

	/**
	 * test if node has children
	 *
	 * @return bool
	 */
	public function hasChildren()
	{
		return (($this->getRightValue() - $this->getLeftValue()) > 1);
	}

	/**
	 * test if node has parent
	 *
	 * @return bool
	 */
	public function hasParent()
	{
		return $this->isValidNode($this->getRecord()) && ! $this->isRoot();
	}

	/**
	 * gets record of prev sibling or empty record
	 *
	 * @return Doctrine_Record
	 */
	public function getPrevSibling()
	{
		$baseAlias = $this->_tree->getBaseAlias();
		$q = $this->_tree->getBaseQuery();
		$q = $q->addWhere("$baseAlias.rgt = ?", $this->getLeftValue() - 1);
		$q = $this->_tree->returnQueryWithRootId($q, $this->getRootValue());
		$result = $q->execute();

		if (count($result) <= 0) {
			return false;
		}

		if ($result instanceof Doctrine_Collection) {
			$sibling = $result->getFirst();
		} else if (is_array($result)) {
			$sibling = array_shift($result);
		}

		return $sibling;
	}

	/**
	 * gets record of next sibling or empty record
	 *
	 * @return Doctrine_Record
	 */
	public function getNextSibling()
	{
		$baseAlias = $this->_tree->getBaseAlias();
		$q = $this->_tree->getBaseQuery();
		$q = $q->addWhere("$baseAlias.lft = ?", $this->getRightValue() + 1);
		$q = $this->_tree->returnQueryWithRootId($q, $this->getRootValue());
		$result = $q->execute();

		if (count($result) <= 0) {
			return false;
		}

		if ($result instanceof Doctrine_Collection) {
			$sibling = $result->getFirst();
		} else if (is_array($result)) {
			$sibling = array_shift($result);
		}

		return $sibling;
	}

	/**
	 * gets siblings for node
	 *
	 * @return array     array of sibling Doctrine_Record objects
	 */
	public function getSiblings($includeNode = false)
	{
		$parent = $this->getParent();
		$siblings = array();
		if ($parent && $parent->exists()) {
			foreach ($parent->getNode()->getChildren() as $child) {
				if ($this->isEqualTo($child) && !$includeNode) {
					continue;
				}
				$siblings[] = $child;
			}
		}
		return $siblings;
	}

	/**
	 * gets record of first child or empty record
	 *
	 * @return Doctrine_Record
	 */
	public function getFirstChild()
	{
		$baseAlias = $this->_tree->getBaseAlias();
		$q = $this->_tree->getBaseQuery();
		$q->addWhere("$baseAlias.lft = ?", $this->getLeftValue() + 1);
		$this->_tree->returnQueryWithRootId($q, $this->getRootValue());
		$result = $q->execute();

		if (count($result) <= 0) {
			return false;
		}

		if ($result instanceof Doctrine_Collection) {
			$child = $result->getFirst();
		} else if (is_array($result)) {
			$child = array_shift($result);
		}

		return $child;
	}

	/**
	 * gets record of last child or empty record
	 *
	 * @return Doctrine_Record
	 */
	public function getLastChild()
	{
		$baseAlias = $this->_tree->getBaseAlias();
		$q = $this->_tree->getBaseQuery();
		$q->addWhere("$baseAlias.rgt = ?", $this->getRightValue() - 1);
		$this->_tree->returnQueryWithRootId($q, $this->getRootValue());
		$result = $q->execute();

		if (count($result) <= 0) {
			return false;
		}

		if ($result instanceof Doctrine_Collection) {
			$child = $result->getFirst();
		} else if (is_array($result)) {
			$child = array_shift($result);
		}

		return $child;
	}

	/**
	 * gets children for node (direct descendants only)
	 *
	 * @return mixed  The children of the node or FALSE if the node has no children.
	 */
	public function getChildren()
	{
		return $this->getDescendants(1);
	}

	/**
	 * gets descendants for node (direct descendants only)
	 *
	 * @return mixed  The descendants of the node or FALSE if the node has no descendants.
	 */
	public function getDescendants($depth = null, $includeNode = false)
	{
		$baseAlias = $this->_tree->getBaseAlias();
		$q = $this->_tree->getBaseQuery();
		$params = array($this->record->get('lft'), $this->record->get('rgt'));

		if ($includeNode) {
			$q->addWhere("$baseAlias.lft >= ? AND $baseAlias.rgt <= ?", $params)->addOrderBy("$baseAlias.lft asc");
		} else {
			$q->addWhere("$baseAlias.lft > ? AND $baseAlias.rgt < ?", $params)->addOrderBy("$baseAlias.lft asc");
		}

		if ($depth !== null) {
			$q->addWhere("$baseAlias.level <= ?", $this->record['level'] + $depth);
		}

		$q = $this->_tree->returnQueryWithRootId($q, $this->getRootValue());
		$result = $q->execute();

		if (count($result) <= 0) {
			return false;
		}

		return $result;
	}

	/**
	 * gets record of parent or empty record
	 *
	 * @return Doctrine_Record
	 */
	public function getParent()
	{
		$baseAlias = $this->_tree->getBaseAlias();
		$q = $this->_tree->getBaseQuery();
		$q->addWhere("$baseAlias.lft < ? AND $baseAlias.rgt > ?", array($this->getLeftValue(), $this->getRightValue()))
		->addWhere("$baseAlias.level >= ?", $this->record['level'] - 1)
		->addOrderBy("$baseAlias.rgt asc");
		$q = $this->_tree->returnQueryWithRootId($q, $this->getRootValue());
		$result = $q->execute();

		if (count($result) <= 0) {
			return false;
		}
		 
		if ($result instanceof Doctrine_Collection) {
			$parent = $result->getFirst();
		} else if (is_array($result)) {
			$parent = array_shift($result);
		}

		return $parent;
	}

	/**
	 * gets ancestors for node
	 *
	 * @param integer $deth  The depth 'upstairs'.
	 * @return mixed  The ancestors of the node or FALSE if the node has no ancestors (this
	 *                basically means it's a root node).
	 */
	public function getAncestors($depth = null)
	{
		$baseAlias = $this->_tree->getBaseAlias();
		$q = $this->_tree->getBaseQuery();
		$q->addWhere("$baseAlias.lft < ? AND $baseAlias.rgt > ?", array($this->getLeftValue(), $this->getRightValue()))
		->addOrderBy("$baseAlias.lft asc");
		if ($depth !== null) {
			$q->addWhere("$baseAlias.level >= ?", $this->record['level'] - $depth);
		}
		$q = $this->_tree->returnQueryWithRootId($q, $this->getRootValue());
		$ancestors = $q->execute();
		if (count($ancestors) <= 0) {
			return false;
		}
		return $ancestors;
	}

	/**
	 * gets path to node from root, uses record::toString() method to get node names
	 *
	 * @param string     $seperator     path seperator
	 * @param bool     $includeNode     whether or not to include node at end of path
	 * @return string     string representation of path
	 */
	public function getPath($seperator = ' > ', $includeRecord = false)
	{
		$path = array();
		$ancestors = $this->getAncestors();
		if ($ancestors) {
			foreach ($ancestors as $ancestor) {
				$path[] = $ancestor->__toString();
			}
		}
		if ($includeRecord) {
			$path[] = $this->getRecord()->__toString();
		}

		return implode($seperator, $path);
	}

	/**
	 * gets number of children (direct descendants)
	 *
	 * @return int
	 */
	public function getNumberChildren()
	{
		$children = $this->getChildren();
		return $children === false ? 0 : count($children);
	}

	/**
	 * gets number of descendants (children and their children)
	 *
	 * @return int
	 */
	public function getNumberDescendants()
	{
		return ($this->getRightValue() - $this->getLeftValue() - 1) / 2;
	}

	/**
	 * inserts node as parent of dest record
	 *
	 * @return bool
	 * @todo Wrap in transaction
	 */
	public function insertAsParentOf(Doctrine_Record $dest)
	{
		// cannot insert a node that has already has a place within the tree
		if ($this->isValidNode()) {
			return false;
		}
		// cannot insert as parent of root
		if ($dest->getNode()->isRoot()) {
			return false;
		}

		// cannot insert as parent of itself
		if (
		$dest === $this->record ||
		($dest->exists() && $this->record->exists() && $dest->identifier() === $this->record->identifier())
		) {
			throw new Doctrine_Tree_Exception("Cannot insert node as parent of itself");

			return false;
		}

		$newLeft  = $dest->getNode()->getLeftValue();
		$newRight = $dest->getNode()->getRightValue() + 2;
		$newRoot  = $dest->getNode()->getRootValue();
		$newLevel = $dest->getNode()->getLevel();

		$conn = $this->record->getTable()->getConnection();
		try {
			$conn->beginInternalTransaction();

			// Make space for new node
			$this->shiftRLValues($dest->getNode()->getRightValue() + 1, 2, $newRoot);

			// Slide child nodes over one and down one to allow new parent to wrap them
			$componentName = $this->_tree->getBaseComponent();
			$q = Doctrine_Core::getTable($componentName)
			->createQuery()
			->update();
			$q->set("$componentName.lft", "$componentName.lft + 1");
			$q->set("$componentName.rgt", "$componentName.rgt + 1");
			$q->set("$componentName.level", "$componentName.level + 1");
			$q->where("$componentName.lft >= ? AND $componentName.rgt <= ?", array($newLeft, $newRight));
			$q = $this->_tree->returnQueryWithRootId($q, $newRoot);
			$q->execute();

			$this->record['level'] = $newLevel;
			$this->insertNode($newLeft, $newRight, $newRoot);

			$conn->commit();
		} catch (Exception $e) {
			$conn->rollback();
			throw $e;
		}

		return true;
	}

	/**
	 * inserts node as previous sibling of dest record
	 *
	 * @return bool
	 * @todo Wrap in transaction
	 */
	public function insertAsPrevSiblingOf(Doctrine_Record $dest)
	{
		// cannot insert a node that has already has a place within the tree
		if ($this->isValidNode()) {
			return false;
		}
		// cannot insert as sibling of itself
		if (
		$dest === $this->record ||
		($dest->exists() && $this->record->exists() && $dest->identifier() === $this->record->identifier())
		) {
			throw new Doctrine_Tree_Exception("Cannot insert node as previous sibling of itself");

			return false;
		}

		$newLeft = $dest->getNode()->getLeftValue();
		$newRight = $dest->getNode()->getLeftValue() + 1;
		$newRoot = $dest->getNode()->getRootValue();

		$conn = $this->record->getTable()->getConnection();
		try {
			$conn->beginInternalTransaction();

			$this->shiftRLValues($newLeft, 2, $newRoot);
			$this->record['level'] = $dest['level'];
			$this->insertNode($newLeft, $newRight, $newRoot);
			// update destination left/right values to prevent a refresh
			// $dest->getNode()->setLeftValue($dest->getNode()->getLeftValue() + 2);
			// $dest->getNode()->setRightValue($dest->getNode()->getRightValue() + 2);

			$conn->commit();
		} catch (Exception $e) {
			$conn->rollback();
			throw $e;
		}

		return true;
	}

	/**
	 * inserts node as next sibling of dest record
	 *
	 * @return bool
	 * @todo Wrap in transaction
	 */
	public function insertAsNextSiblingOf(Doctrine_Record $dest)
	{
		// cannot insert a node that has already has a place within the tree
		if ($this->isValidNode()) {
			return false;
		}
		// cannot insert as sibling of itself
		if (
		$dest === $this->record ||
		($dest->exists() && $this->record->exists() && $dest->identifier() === $this->record->identifier())
		) {
			throw new Doctrine_Tree_Exception("Cannot insert node as next sibling of itself");

			return false;
		}

		$newLeft = $dest->getNode()->getRightValue() + 1;
		$newRight = $dest->getNode()->getRightValue() + 2;
		$newRoot = $dest->getNode()->getRootValue();

		$conn = $this->record->getTable()->getConnection();
		try {
			$conn->beginInternalTransaction();

			$this->shiftRLValues($newLeft, 2, $newRoot);
			$this->record['level'] = $dest['level'];
			$this->insertNode($newLeft, $newRight, $newRoot);
			// update destination left/right values to prevent a refresh
			// no need, node not affected

			$conn->commit();
		} catch (Exception $e) {
			$conn->rollback();
			throw $e;
		}

		return true;
	}

	/**
	 * inserts node as first child of dest record
	 *
	 * @return bool
	 * @todo Wrap in transaction
	 */
	public function insertAsFirstChildOf(Doctrine_Record $dest)
	{
		// cannot insert a node that has already has a place within the tree
		if ($this->isValidNode()) {
			return false;
		}
		// cannot insert as child of itself
		if (
		$dest === $this->record ||
		($dest->exists() && $this->record->exists() && $dest->identifier() === $this->record->identifier())
		) {
			throw new Doctrine_Tree_Exception("Cannot insert node as first child of itself");

			return false;
		}

		$newLeft = $dest->getNode()->getLeftValue() + 1;
		$newRight = $dest->getNode()->getLeftValue() + 2;
		$newRoot = $dest->getNode()->getRootValue();

		$conn = $this->record->getTable()->getConnection();
		try {
			$conn->beginInternalTransaction();

			$this->shiftRLValues($newLeft, 2, $newRoot);
			$this->record['level'] = $dest['level'] + 1;
			$this->insertNode($newLeft, $newRight, $newRoot);

			// update destination left/right values to prevent a refresh
			// $dest->getNode()->setRightValue($dest->getNode()->getRightValue() + 2);

			$conn->commit();
		} catch (Exception $e) {
			$conn->rollback();
			throw $e;
		}

		return true;
	}

	/**
	 * inserts node as last child of dest record
	 *
	 * @return bool
	 * @todo Wrap in transaction
	 */
	public function insertAsLastChildOf(Doctrine_Record $dest)
	{
		// cannot insert a node that has already has a place within the tree
		if ($this->isValidNode()) {
			return false;
		}
		// cannot insert as child of itself
		if (
		$dest === $this->record ||
		($dest->exists() && $this->record->exists() && $dest->identifier() === $this->record->identifier())
		) {
			throw new Doctrine_Tree_Exception("Cannot insert node as last child of itself");

			return false;
		}

		$newLeft = $dest->getNode()->getRightValue();
		$newRight = $dest->getNode()->getRightValue() + 1;
		$newRoot = $dest->getNode()->getRootValue();

		$conn = $this->record->getTable()->getConnection();
		try {
			$conn->beginInternalTransaction();

			$this->shiftRLValues($newLeft, 2, $newRoot);
			$this->record['level'] = $dest['level'] + 1;
			$this->insertNode($newLeft, $newRight, $newRoot);

			// update destination left/right values to prevent a refresh
			// $dest->getNode()->setRightValue($dest->getNode()->getRightValue() + 2);

			$conn->commit();
		} catch (Exception $e) {
			$conn->rollback();
			throw $e;
		}

		return true;
	}

	/**
	 * Accomplishes moving of nodes between different trees.
	 * Used by the move* methods if the root values of the two nodes are different.
	 *
	 * @param Doctrine_Record $dest
	 * @param unknown_type $newLeftValue
	 * @param unknown_type $moveType
	 * @todo Better exception handling/wrapping
	 */
	private function _moveBetweenTrees(Doctrine_Record $dest, $newLeftValue, $moveType)
	{
		$conn = $this->record->getTable()->getConnection();

		try {
			$conn->beginInternalTransaction();

			// Move between trees: Detach from old tree & insert into new tree
			$newRoot = $dest->getNode()->getRootValue();
			$oldRoot = $this->getRootValue();
			$oldLft = $this->getLeftValue();
			$oldRgt = $this->getRightValue();
			$oldLevel = $this->record['level'];

			// Prepare target tree for insertion, make room
			$this->shiftRlValues($newLeftValue, $oldRgt - $oldLft - 1, $newRoot);

			// Set new root id for this node
			$this->setRootValue($newRoot);
			$this->record->save();

			// Insert this node as a new node
			$this->setRightValue(0);
			$this->setLeftValue(0);

			switch ($moveType) {
				case 'moveAsPrevSiblingOf':
					$this->insertAsPrevSiblingOf($dest);
					break;
				case 'moveAsFirstChildOf':
					$this->insertAsFirstChildOf($dest);
					break;
				case 'moveAsNextSiblingOf':
					$this->insertAsNextSiblingOf($dest);
					break;
				case 'moveAsLastChildOf':
					$this->insertAsLastChildOf($dest);
					break;
				default:
					throw new Doctrine_Node_Exception("Unknown move operation: $moveType.");
			}

			$diff = $oldRgt - $oldLft;
			$this->setRightValue($this->getLeftValue() + ($oldRgt - $oldLft));
			$this->record->save();

			$newLevel = $this->record['level'];
			$levelDiff = $newLevel - $oldLevel;

			// Relocate descendants of the node
			$diff = $this->getLeftValue() - $oldLft;
			$componentName = $this->_tree->getBaseComponent();
			$rootColName = $this->_tree->getAttribute('rootColumnName');

			// Update lft/rgt/root/level for all descendants
			$q = Doctrine_Core::getTable($componentName)
			->createQuery()
			->update()
			->set($componentName . '.lft', $componentName.'.lft + ?', $diff)
			->set($componentName . '.rgt', $componentName.'.rgt + ?', $diff)
			->set($componentName . '.level', $componentName.'.level + ?', $levelDiff)
			->set($componentName . '.' . $rootColName, '?', $newRoot)
			->where($componentName . '.lft > ? AND ' . $componentName . '.rgt < ?', array($oldLft, $oldRgt));
			$q = $this->_tree->returnQueryWithRootId($q, $oldRoot);
			$q->execute();

			// Close gap in old tree
			$first = $oldRgt + 1;
			$delta = $oldLft - $oldRgt - 1;
			$this->shiftRLValues($first, $delta, $oldRoot);

			$conn->commit();
			 
			return true;
		} catch (Exception $e) {
			$conn->rollback();
			throw $e;
		}

		return false;
	}

	/**
	 * moves node as prev sibling of dest record
	 *
	 */
	public function moveAsPrevSiblingOf(Doctrine_Record $dest)
	{
		if (
		$dest === $this->record ||
		($dest->exists() && $this->record->exists() && $dest->identifier() === $this->record->identifier())
		) {
			throw new Doctrine_Tree_Exception("Cannot move node as previous sibling of itself");

			return false;
		}

		if ($dest->getNode()->getRootValue() != $this->getRootValue()) {
			// Move between trees
			return $this->_moveBetweenTrees($dest, $dest->getNode()->getLeftValue(), __FUNCTION__);
		} else {
			// Move within the tree
			$oldLevel = $this->record['level'];
			$this->record['level'] = $dest['level'];
			$this->updateNode($dest->getNode()->getLeftValue(), $this->record['level'] - $oldLevel);
		}

		return true;
	}

	/**
	 * moves node as next sibling of dest record
	 *
	 */
	public function moveAsNextSiblingOf(Doctrine_Record $dest)
	{
		if (
		$dest === $this->record ||
		($dest->exists() && $this->record->exists() && $dest->identifier() === $this->record->identifier())
		) {
			throw new Doctrine_Tree_Exception("Cannot move node as next sibling of itself");

			return false;
		}

		if ($dest->getNode()->getRootValue() != $this->getRootValue()) {
			// Move between trees
			return $this->_moveBetweenTrees($dest, $dest->getNode()->getRightValue() + 1, __FUNCTION__);
		} else {
			// Move within tree
			$oldLevel = $this->record['level'];
			$this->record['level'] = $dest['level'];
			$this->updateNode($dest->getNode()->getRightValue() + 1, $this->record['level'] - $oldLevel);
		}

		return true;
	}

	/**
	 * moves node as first child of dest record
	 *
	 */
	public function moveAsFirstChildOf(Doctrine_Record $dest)
	{
		if (
		$dest === $this->record || $this->isAncestorOf($dest) ||
		($dest->exists() && $this->record->exists() && $dest->identifier() === $this->record->identifier())
		) {
			throw new Doctrine_Tree_Exception("Cannot move node as first child of itself or into a descendant");

			return false;
		}

		if ($dest->getNode()->getRootValue() != $this->getRootValue()) {
			// Move between trees
			return $this->_moveBetweenTrees($dest, $dest->getNode()->getLeftValue() + 1, __FUNCTION__);
		} else {
			// Move within tree
			$oldLevel = $this->record['level'];
			$this->record['level'] = $dest['level'] + 1;
			$this->updateNode($dest->getNode()->getLeftValue() + 1, $this->record['level'] - $oldLevel);
		}

		return true;
	}

	/**
	 * moves node as last child of dest record
	 *
	 */
	public function moveAsLastChildOf(Doctrine_Record $dest)
	{
		if (
		$dest === $this->record || $this->isAncestorOf($dest) ||
		($dest->exists() && $this->record->exists() && $dest->identifier() === $this->record->identifier())
		) {
			throw new Doctrine_Tree_Exception("Cannot move node as last child of itself or into a descendant");

			return false;
		}

		if ($dest->getNode()->getRootValue() != $this->getRootValue()) {
			// Move between trees
			return $this->_moveBetweenTrees($dest, $dest->getNode()->getRightValue(), __FUNCTION__);
		} else {
			// Move within tree
			$oldLevel = $this->record['level'];
			$this->record['level'] = $dest['level'] + 1;
			$this->updateNode($dest->getNode()->getRightValue(), $this->record['level'] - $oldLevel);
		}

		return true;
	}

	/**
	 * Makes this node a root node. Only used in multiple-root trees.
	 *
	 * @todo Exception handling/wrapping
	 */
	public function makeRoot($newRootId)
	{
		// TODO: throw exception instead?
		if ($this->getLeftValue() == 1 || ! $this->_tree->getAttribute('hasManyRoots')) {
			return false;
		}

		$oldRgt = $this->getRightValue();
		$oldLft = $this->getLeftValue();
		$oldRoot = $this->getRootValue();
		$oldLevel = $this->record['level'];

		$conn = $this->record->getTable()->getConnection();
		try {
			$conn->beginInternalTransaction();

			// Update descendants lft/rgt/root/level values
			$diff = 1 - $oldLft;
			$newRoot = $newRootId;
			$componentName = $this->_tree->getBaseComponent();
			$rootColName = $this->_tree->getAttribute('rootColumnName');
			$q = Doctrine_Core::getTable($componentName)
			->createQuery()
			->update()
			->set($componentName . '.lft', $componentName.'.lft + ?', array($diff))
			->set($componentName . '.rgt', $componentName.'.rgt + ?', array($diff))
			->set($componentName . '.level', $componentName.'.level - ?', array($oldLevel))
			->set($componentName . '.' . $rootColName, '?', array($newRoot))
			->where($componentName . '.lft > ? AND ' . $componentName . '.rgt < ?', array($oldLft, $oldRgt));
			$q = $this->_tree->returnQueryWithRootId($q, $oldRoot);
			$q->execute();

			// Detach from old tree (close gap in old tree)
			$first = $oldRgt + 1;
			$delta = $oldLft - $oldRgt - 1;
			$this->shiftRLValues($first, $delta, $this->getRootValue());

			// Set new lft/rgt/root/level values for root node
			$this->setLeftValue(1);
			$this->setRightValue($oldRgt - $oldLft + 1);
			$this->setRootValue($newRootId);
			$this->record['level'] = 0;

			$this->record->save();

			$conn->commit();

			return true;
		} catch (Exception $e) {
			$conn->rollback();
			throw $e;
		}

		return false;
	}

	/**
	 * adds node as last child of record
	 *
	 */
	public function addChild(Doctrine_Record $record)
	{
		$record->getNode()->insertAsLastChildOf($this->getRecord());
	}

	/**
	 * determines if node is leaf
	 *
	 * @return bool
	 */
	public function isLeaf()
	{
		return (($this->getRightValue() - $this->getLeftValue()) == 1);
	}

	/**
	 * determines if node is root
	 *
	 * @return bool
	 */
	public function isRoot()
	{
		return ($this->getLeftValue() == 1);
	}

	/**
	 * determines if node is equal to subject node
	 *
	 * @return bool
	 */
	public function isEqualTo(Doctrine_Record $subj)
	{
		return (($this->getLeftValue() == $subj->getNode()->getLeftValue()) &&
		($this->getRightValue() == $subj->getNode()->getRightValue()) &&
		($this->getRootValue() == $subj->getNode()->getRootValue())
		);
	}

	/**
	 * determines if node is child of subject node
	 *
	 * @return bool
	 */
	public function isDescendantOf(Doctrine_Record $subj)
	{
		return (($this->getLeftValue() > $subj->getNode()->getLeftValue()) &&
		($this->getRightValue() < $subj->getNode()->getRightValue()) &&
		($this->getRootValue() == $subj->getNode()->getRootValue()));
	}

	/**
	 * determines if node is child of or sibling to subject node
	 *
	 * @return bool
	 */
	public function isDescendantOfOrEqualTo(Doctrine_Record $subj)
	{
		return (($this->getLeftValue() >= $subj->getNode()->getLeftValue()) &&
		($this->getRightValue() <= $subj->getNode()->getRightValue()) &&
		($this->getRootValue() == $subj->getNode()->getRootValue()));
	}

	/**
	 * determines if node is ancestor of subject node
	 *
	 * @return bool
	 */
	public function isAncestorOf(Doctrine_Record $subj)
	{
		return (($subj->getNode()->getLeftValue() > $this->getLeftValue()) &&
		($subj->getNode()->getRightValue() < $this->getRightValue()) &&
		($subj->getNode()->getRootValue() == $this->getRootValue()));
	}

	/**
	 * determines if node is valid
	 *
	 * @return bool
	 */
	public function isValidNode($record = null)
	{
		if ($record === null) {
			return ($this->getRightValue() > $this->getLeftValue());
		} else if ( $record instanceof Doctrine_Record ) {
			return ($record->getNode()->getRightValue() > $record->getNode()->getLeftValue());
		} else {
			return false;
		}
	}

	/**
	 * Detaches the node from the tree by invalidating it's lft & rgt values
	 * (they're set to 0).
	 */
	public function detach()
	{
		$this->setLeftValue(0);
		$this->setRightValue(0);
	}

	/**
	 * deletes node and it's descendants
	 * @todo Delete more efficiently. Wrap in transaction if needed.
	 */
	public function delete()
	{
		$conn = $this->record->getTable()->getConnection();
		try {
			$conn->beginInternalTransaction();

			// TODO: add the setting whether or not to delete descendants or relocate children
			$oldRoot = $this->getRootValue();
			$q = $this->_tree->getBaseQuery();

			$baseAlias = $this->_tree->getBaseAlias();
			$componentName = $this->_tree->getBaseComponent();

			$q = $q->addWhere("$baseAlias.lft >= ? AND $baseAlias.rgt <= ?", array($this->getLeftValue(), $this->getRightValue()));

			$q = $this->_tree->returnQueryWithRootId($q, $oldRoot);

			$coll = $q->execute();

			$coll->delete();

			$first = $this->getRightValue() + 1;
			$delta = $this->getLeftValue() - $this->getRightValue() - 1;
			$this->shiftRLValues($first, $delta, $oldRoot);

			$conn->commit();
		} catch (Exception $e) {
			$conn->rollback();
			throw $e;
		}

		return true;
	}

	/**
	 * sets node's left and right values and save's it
	 *
	 * @param int     $destLeft     node left value
	 * @param int        $destRight    node right value
	 */
	private function insertNode($destLeft = 0, $destRight = 0, $destRoot = 1)
	{
		$this->setLeftValue($destLeft);
		$this->setRightValue($destRight);
		$this->setRootValue($destRoot);
		$this->record->save();
	}

	/**
	 * move node's and its children to location $destLeft and updates rest of tree
	 *
	 * @param int     $destLeft    destination left value
	 * @todo Wrap in transaction
	 */
	private function updateNode($destLeft, $levelDiff)
	{
		$componentName = $this->_tree->getBaseComponent();
		$left = $this->getLeftValue();
		$right = $this->getRightValue();
		$rootId = $this->getRootValue();

		$treeSize = $right - $left + 1;

		$conn = $this->record->getTable()->getConnection();
		try {
			$conn->beginInternalTransaction();

			// Make room in the new branch
			$this->shiftRLValues($destLeft, $treeSize, $rootId);

			if ($left >= $destLeft) { // src was shifted too?
				$left += $treeSize;
				$right += $treeSize;
			}

			// update level for descendants
			$q = Doctrine_Core::getTable($componentName)
			->createQuery()
			->update()
			->set($componentName . '.level', $componentName.'.level + ?', array($levelDiff))
			->where($componentName . '.lft > ? AND ' . $componentName . '.rgt < ?', array($left, $right));
			$q = $this->_tree->returnQueryWithRootId($q, $rootId);
			$q->execute();

			// now there's enough room next to target to move the subtree
			$this->shiftRLRange($left, $right, $destLeft - $left, $rootId);

			// correct values after source (close gap in old tree)
			$this->shiftRLValues($right + 1, -$treeSize, $rootId);

			$this->record->save();
			$this->record->refresh();

			$conn->commit();
		} catch (Exception $e) {
			$conn->rollback();
			throw $e;
		}

		return true;
	}

	/**
	 * adds '$delta' to all Left and Right values that are >= '$first'. '$delta' can also be negative.
	 *
	 * Note: This method does wrap its database queries in a transaction. This should be done
	 * by the invoking code.
	 *
	 * @param int $first         First node to be shifted
	 * @param int $delta         Value to be shifted by, can be negative
	 */
	private function shiftRlValues($first, $delta, $rootId = 1)
	{
		// shift left columns
		$componentName = $this->_tree->getBaseComponent();

		$qLeft  = Doctrine_Core::getTable($componentName)
		->createQuery()
		->update($componentName);

		$qRight = Doctrine_Core::getTable($componentName)
		->createQuery()
		->update($componentName);

		$qLeft = $qLeft->set($componentName . '.lft', $componentName.'.lft + ?', $delta)
		->where($componentName . '.lft >= ?', $first);
		$qLeft = $this->_tree->returnQueryWithRootId($qLeft, $rootId);

		$resultLeft = $qLeft->execute();

		// shift right columns
		$qRight = $qRight->set($componentName . '.rgt', $componentName.'.rgt + ?', $delta)
		->where($componentName . '.rgt >= ?', $first);

		$qRight = $this->_tree->returnQueryWithRootId($qRight, $rootId);

		$resultRight = $qRight->execute();
	}

	/**
	 * adds '$delta' to all Left and Right values that are >= '$first' and <= '$last'.
	 * '$delta' can also be negative.
	 *
	 * Note: This method does wrap its database queries in a transaction. This should be done
	 * by the invoking code.
	 *
	 * @param int $first     First node to be shifted (L value)
	 * @param int $last     Last node to be shifted (L value)
	 * @param int $delta         Value to be shifted by, can be negative
	 */
	private function shiftRlRange($first, $last, $delta, $rootId = 1)
	{
		$componentName = $this->_tree->getBaseComponent();

		$qLeft  = Doctrine_Core::getTable($componentName)
		->createQuery()
		->update();

		$qRight = Doctrine_Core::getTable($componentName)
		->createQuery()
		->update();

		// shift left column values
		$qLeft = $qLeft->set($componentName . '.lft', $componentName.'.lft + ?', $delta)
		->where($componentName . '.lft >= ? AND ' . $componentName . '.lft <= ?', array($first, $last));

		$qLeft = $this->_tree->returnQueryWithRootId($qLeft, $rootId);

		$resultLeft = $qLeft->execute();

		// shift right column values
		$qRight = $qRight->set($componentName . '.rgt', $componentName.'.rgt + ?', $delta)
		->where($componentName . '.rgt >= ? AND ' . $componentName . '.rgt <= ?', array($first, $last));

		$qRight = $this->_tree->returnQueryWithRootId($qRight, $rootId);

		$resultRight = $qRight->execute();
	}

	/**
	 * gets record's left value
	 *
	 * @return int
	 */
	public function getLeftValue()
	{
		return $this->record->get('lft');
	}

	/**
	 * sets record's left value
	 *
	 * @param int
	 */
	public function setLeftValue($lft)
	{
		$this->record->set('lft', $lft);
	}

	/**
	 * gets record's right value
	 *
	 * @return int
	 */
	public function getRightValue()
	{
		return $this->record->get('rgt');
	}

	/**
	 * sets record's right value
	 *
	 * @param int
	 */
	public function setRightValue($rgt)
	{
		$this->record->set('rgt', $rgt);
	}

	/**
	 * gets level (depth) of node in the tree
	 *
	 * @return int
	 */
	public function getLevel()
	{
		if ( ! isset($this->record['level'])) {
			$baseAlias = $this->_tree->getBaseAlias();
			$componentName = $this->_tree->getBaseComponent();
			$q = $this->_tree->getBaseQuery();
			$q = $q->addWhere("$baseAlias.lft < ? AND $baseAlias.rgt > ?", array($this->getLeftValue(), $this->getRightValue()));

			$q = $this->_tree->returnQueryWithRootId($q, $this->getRootValue());

			$coll = $q->execute();

			$this->record['level'] = count($coll) ? count($coll) : 0;
		}
		return $this->record['level'];
	}

	/**
	 * get records root id value
	 *
	 */
	public function getRootValue()
	{
		if ($this->_tree->getAttribute('hasManyRoots')) {
			return $this->record->get($this->_tree->getAttribute('rootColumnName'));
		}
		return 1;
	}

	/**
	 * sets records root id value
	 *
	 * @param int
	 */
	public function setRootValue($value)
	{
		if ($this->_tree->getAttribute('hasManyRoots')) {
			$this->record->set($this->_tree->getAttribute('rootColumnName'), $value);
		}
	}
}
